STARK DPM 整理
libstark内のDNA profile matchシステムの仕様整理。
ブロック暗号：Rijndeal
圧縮変換：Davies-Meyer
iteration構造：Merkle-Damgård
Davies-Meyer
$ hash(B, K) = E_K(B) xor B
レジスタ整理
B: Rijndeal-160暗号のoutputを計算する間のB(160bits)の保持。 (Davies-Meyer的に）
K: keyのstateレジスタ20個、それぞれ160bits
INV1~5: RijndealのSubBytesでinverseを計算するためのauxiliary field elements
Wi1~3: INVで繰り返される4乗計算のために利用
FLAG1, FLAG2: rijndeal loopのために利用
RC: Rcon(i)の計算に利用、iはRijndealのloop
invRC: Rijndeal iterationsをいつストップするか伝えるためのRCのinverseで利用
A, B, C:
STATE: 外部状態のためのflag
K :
MATCH:
isSecondPhaseComparingLOCI:
PartialMATCH:
PHASE:
L1~5 (+6?): databaseから新たに渡されたSTRペアを比較するためのロジック実行に利用
ST2, ST3: (PAIR1とPAIR2？）
全体の流れ
public inputのコミットメントが確かにprivate inputのdataと一致するか検証する。
profileのコミットメントがprivate inputのprofileのハッシュ値と一致するかをまず検証（databaseに入ってるか以前に）
ハッシュチェーンの最後のコミットメントがdatabaseのコミットメントと一致するか
それぞれのprofileは40bytes長
https://gyazo.com/092469df8dbbcd40a9efd45b90f53ee4
チェックペア部分のロジック
https://gyazo.com/f9ba5ebee0b47d6d2740225cdfa813ec
マッチングResult部分のロジック
https://gyazo.com/2c10d8bbb4e44289eddedb64fce78299
databaseは以下のようにN個のハッシュチェーンとして記録されているとする。 XVでboundary constraintとして検証している。
https://gyazo.com/635e8564fc64f04b49247ab8dc26d11c
chainのそれぞれの要素はCODIS (Combined DNA Index System)のフォーマットにしたがって、20個の"core loci"のセットで測られるDNAのSTR (Short Tndem Repeat) countで表現されている。
１つのDNA profileは1つのlociに対して2つの20個ペアSTR値を必要とするので、それぞれのprofileはhashchainの連続する2つの要素として記録されている。
つまり、n profilesのdatabaseは2nのchain elementsが必要になる。
(1,1),(1,2)...(10,1)(10,2)をチェック -> (11,1)...(20,2)をチェック
outputについて
perfect match
partial match
no match
RijndealとDavies-Meyer周り
Rijndeal-160は11ラウンド行う。（最後のラウンドのMixColumunsは省略）
それぞれのラウンドで5cycle行うので、合計55cycleのRijndeal-160。
計算のwidthは65なので、証明者は55*65 = 3575 要素を1回のRijndeal-160で必要とする。（DM変換の1回）
Rijndealは$ F_{2^8}上での計算なのに対し、IOPシステムは$ F_{2^{64}}上で計算（つまり、異なるプリミティブ多項式を使っている）なので、同型写像する必要がある。（$ F_{2^{64}}が部分体）
.$ F_{2^{64}}の$ 2^8-1のオーダーの要素を使うことで、部分体である$ F_{2^{64}}の要素を$ F_{2^{8}}の要素にマッピングできる。
Davies-Meyer変換の中でRijndeal-160暗号が使われているので、1回の変換で160 bitsをoutput （平文を160bitsずつ分割して、inputし、以前のhash値(160bits)もinput（計320bits)）する。
しかし、1つのレジスタは8bitsしか入れられないので
https://gyazo.com/82cec9cc977dd5438bfa7deec84818c1
https://gyazo.com/ef12f7dc004ece9f318805593cd5f545
https://gyazo.com/6484b018574060ff988a17eac596d2bb